package com.matt.quicksort;

import java.util.Arrays;

public class QuickSort 
{

	public void sort(int[] array, int left, int right)
	{
		System.out.println("quick sort array: " + Arrays.toString(array));
		
		if(left < right)
		{
			int q = partitioin(array, left, right);
			if(left < q - 1)
				sort(array, left, q -1);
			if(q < right)
				sort(array, q, right);			
		}
	}
	
	private int partitioin(int[] arr, int left, int right)
	{
		System.out.println("partition arr: " + Arrays.toString(arr) + ", left: " + left + ", right: " + right);
		
		int pivot = arr[ (left + right) / 2 ];
		int i = left, j = right;
		
		while(i <= j)
		{
			while(arr[i] < pivot)
				i++;
			while(arr[j] > pivot)
				j--;
			
			if(i <= j)
			{
				swap(arr, i, j);
				i++;
				j--;
			}
		}
		
		return i;
	}
	
	private void swap(int[] arr, int elemA, int elemB)
	{
		int temp = arr[elemA];
		arr[elemA] = arr[elemB];
		arr[elemB] = temp;
		System.out.println("swap arr: " + Arrays.toString(arr));
	}

}
